// https://www.lintcode.com/problem/unique-binary-search-trees-ii/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @paramn n: An integer
     * @return: A list of root
     */
    public List<TreeNode> generateTrees(int n) {
        // write your code here
        List<TreeNode> ret = new ArrayList<>();
        if (n == 0) {
          ret.add(null);
          return ret;
        }
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
          a[i] = i + 1;
        }
        ret = _generateTrees(a, 0, a.length);
        return ret;
    }

    protected List<TreeNode> _generateTrees(int[] a, int start, int end) {
      List<TreeNode> trees = new ArrayList<>();
      for (int i = start; i < end; ++i) {
        List<TreeNode> lts = new ArrayList<>();
        List<TreeNode> rts = new ArrayList<>();
        if (i > 0) {
          lts = _generateTrees(a, start, i);
        }
        if (i < (end - 1)) {
          rts = _generateTrees(a, i + 1, end);
        }
        if (lts.size() == 0) {
          lts.add(null);
        }
        if (rts.size() == 0) {
          rts.add(null);
        }
        for (TreeNode lt : lts) {
          for (TreeNode rt : rts) {
            TreeNode root = new TreeNode(a[i]);
            root.left = lt;
            root.right = rt;
            trees.add(root);
          }
        }
      }
      return trees;
    }
}